#include<iostream>
using namespace std;
#include<string>
#include<vector>
vector<string> restoreIpAddresses(string s) {
    int n = s.size();
    // dp[i][k] 表示前 i 个字符组成 k 段时的所有可能
    vector<vector<vector<string>>> dp(n + 1, vector<vector<string>>(5));

    dp[0][0] = { "" }; // 初始状态：0 个字符，0 段，空串

    for (int i = 1; i <= n; i++) {          // 遍历前 i 个字符
        for (int k = 1; k <= 4; k++) {      // 段数（1~4）
            for (int len = 1; len <= 3; len++) { // 段长度（1~3）
                if (i - len < 0) continue;
                string seg = s.substr(i - len, len);

                // 判断是否合法段
                if ((seg.size() > 1 && seg[0] == '0') || stoi(seg) > 255)
                    continue;

                // 拼接到 dp[i-len][k-1] 的组合后面
                for (string prev : dp[i - len][k - 1]) {
                    if (prev.empty())
                        dp[i][k].push_back(seg);
                    else
                        dp[i][k].push_back(prev + "." + seg);
                }
            }
        }
    }

    return dp[n][4]; // n 个字符，4 段，返回所有组合
}


int main()
{
    string s = "25525511135";
    restoreIpAddresses(s);
    return 0;
}